package com.algorithm.classics150.栈;

import java.util.Deque;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Stack;

public class 有效的括号_20 {

    public boolean isValid(String s) {
        int l = s.length();
        //判断是否是成对的
        if (l % 2 == 1){
            return false;
        }
        // 括号映射
        HashMap<Character, Character> map = new HashMap<>();
        map.put(')','(');
        map.put(']','[');
        map.put('}','{');
        Stack<Character> stack = new Stack<Character>();
        for (int i = 0;i<l;i++){
            char ch = s.charAt(i);
            if (map.containsKey(ch)){
                //判断存在且栈不为空则对比是否对应
                if (stack.isEmpty() || stack.peek() != map.get(ch)){
                    return false;
                }
                stack.pop();
            }else {
                stack.push(ch);
            }
        }
        //最后如果都出栈了，则返回true
        return stack.isEmpty();
    }
    /**
     * 时间复杂度：O(n)，其中 n 是字符串 s 的长度。
     */
}
